1. Field of the Invention
The invention relates generally to the problem of filtering information and more particularly to the problem of filtering information in time-critical contexts.
2. Description of Related Art
A common task to which digital systems are put is filtering information. At the simplest level, digital systems filter information by rejecting input that must be wrong. For example, if a fill-in form requires a numeric value for a field and a user inputs a non-numeric value in the field, the system may be programmed to reject the non-numeric value. At a somewhat more complicated level, a digital system may need to determine the context to which the sequence of characters being input at the keyboard belongs: for example, is the sequence intended for a document that the user is editing, or is it intended to be input to a dialog box as a search string?
Clearly, the more complex the information being filtered is and the more contexts the information may be applied to, the more difficult it is to filter the information correctly and quickly. FIG. 4 gives a general overview of the information filtering problem. Filtering system 401 has an information filter 407 which receives an information item 403 which includes values 405(1 . . . n) and provides subsets 411(1 . . . k) of those values 405 to a number of different contexts 409(1 . . . k), with each subset 411(i) containing exactly those values 405 which are required for context 409(i). Information item 403 may be one of many information items belonging to different types 404, with the type 404 of the information item determining the kinds of values which make up the set of values contained in the information item. When this is the case, information filter 407 must determine which of the contexts 409 an information item 403(i) with type 404(k) is relevant to and having done that, which values from the set of information 406 for type 404(k) are relevant to each of those contexts.
Traditionally, an information filter 407 has been implemented as a computer program: the programmer who writes filter 407 knows which types of information items are relevant to which contexts and also knows which values of a relevant type are relevant values for a context. The program keeps track of which contexts are active, and when an item of information comes in, the program determines from the item's type which of the active contexts the item of information is relevant to and then selects the values from the item of information that are relevant to a particular context and provides them to the context. One problem with implementing information filter 407 as a program is that as the number of contexts and/or the number of types of information items increase, the size and complexity of the program increase rapidly. As the size and complexity of the program increase, so does the cost of writing it, and because big, complex programs have more bugs than small, simple ones, the cost of maintaining the program increases as well. Another, more important, problem is that the program that implements information filter 407 has been written for a specific combination of information item types and contexts and cannot be used for any other combination of information item types and contexts. The combination of information item types and contexts for which the program is written is termed the program's domain, and computer programs are by their very nature domain specific and must be completely rewritten to work in a different domain. Moreover, because the program is tailored to a specific set of information types and a specific set of contexts, the domain to which it is specific is tightly constrained, and consequently, what appear to a user to be small changes in the set of information types or in the set of contexts may still require extensive changes to the program.
Another way of implementing an information filter is to use a knowledge base to determine which types of information items are relevant to which contexts and which values of a particular type are relevant to a particular context. Knowledge is the objects, concepts and relationships that exist in some area of interest. The area of interest is the knowledge base's domain. The knowledge base is a collection of knowledge which is represented using some knowledge representation language. To give a simple example, the information item being filtered might be a description of a medevac helicopter in flight. The values included in the description might include the helicopter's type, capacity, heading, speed, and altitude. The knowledge base might include a class aerial vehicle with a subclass helicopter that itself has two subclasses, medevac helicopter and attack helicopter. The class aerial vehicle has the attributes “position, heading, speed, and altitude”; the subclass helicopter inherits the attributes of the class aerial vehicle and may further have the attribute “VTOL”; the subclasses of helicopter inherit the helicopter attributes and the subclass medevac helicopter may further include the attribute “non-ambulant capacity”, while the subclass attack helicopter may further include the attributes “armament” and “troop capacity”. The medevac helicopter is further a subclass of emergency vehicle, whose attributes are “non-ambulant capacity”, “position” and “speed”. The knowledge base might further include classes of context including an air traffic control context and an emergency evacuation context. All aerial vehicles, and therefore all helicopters, are relevant to the air traffic control context, but the only information that is relevant is the helicopter's position, heading, speed, and altitude. In the emergency evacuation context, all emergency vehicles are relevant, but since only medevac helicopters are emergency vehicles, medevac helicopters are the only kind of helicopter that is relevant to the emergency evacuation context. In this context, the relevant information is position, speed, and non-ambulant capacity. To filter the attribute values for the medevac helicopter, a program can determine from the context information in the knowledge base whether the context is the emergency evacuation context or the air traffic control context and can provide the values for those portions of the attributes that are relevant to the context.
The chief advantage of this approach is that the domain-specific information is in the knowledge base. The program doing the filtering need only be able to work generally with knowledge bases. Thus, changing the domain of the filtering is now a matter of using a different knowledge base rather than rewriting the program. Though construction of a knowledge base is not easy, it requires only an understanding of the relationships between the objects in the knowledge base, while writing a filtering program requires that understanding as well as the capacity to correctly implement a complex computer program. Making and debugging knowledge bases is thus easier and cheaper than making and debugging computer programs. The disadvantage of using knowledge bases to filter data has been that the process of determining what superclasses a subclass belongs to and determining which superclass relates to the context has been slow. In particular, filtering systems using knowledge bases have been too slow to use in applications where rapid responses have been required. One set of such applications is applications such as air traffic control or emergency management; another is applications which train humans to react properly in situations where rapid human reactions are required.
From the foregoing, it may be seen that what is needed in this area is an information filtering system that employs a knowledge base and can filter information quickly enough to be useful in time-critical applications. It is an object of the present invention to provide such an information filtering system.